package praktikum_3_ylesanded.ylesanne_1;

import java.util.ArrayList;

/**
 * Created by IntelliJ IDEA.
 * User: Jaan Sepp and Martti Elias
 * Date: 13.11.11
 * Time: 20:50
 */
public class Knapsack {
  private int maxProfit;
  private int maxWeight;
  private int[] itemWeights;
  private int[] itemProfits;
  private ArrayList<Integer> bestList;
  private int numberOfItems;  //(first item is dummy 0)
  private PriorityQueue priorityQueue;

   /**
  * Best first branch and bound algorithm
  * @param n Number of items
  * @param w Array of weights
  * @param p Array of profits
  * @param W Max allowed weight
  * @return maxProfit
  */
  public int knapsackBestFirst(int n, int[] w, int[] p, int W) {
    numberOfItems = n;
    itemWeights = w;
    itemProfits = p;
    maxWeight = W;
    bestList = new ArrayList<Integer>();
    priorityQueue = new PriorityQueue();
    Node root = new Node();
    root.level = 0;
    root.weight = 0;
    root.profit = 0;
    root.bound = 0;
    root.copyList(null);
    priorityQueue.enqueue(root);
    knapsack();
    return maxProfit;
  }

  private void knapsack() {
    while (!priorityQueue.isEmpty()) {
      Node current = priorityQueue.dequeue( );
        if (current.bound > maxProfit) {
          Node firstChild = new Node( );
          firstChild.level = current.level + 1;
          firstChild.weight = current.weight + itemWeights[current.level+1];
          firstChild.profit = current.profit + itemProfits[current.level+1];
          firstChild.copyList(current.contains);
          firstChild.add(current.level + 1);
          if (firstChild.weight < maxWeight && firstChild.profit > maxProfit)  {
            maxProfit = firstChild.profit;
            bestList = new ArrayList<Integer>(firstChild.contains);
          }
          firstChild.bound = bound(firstChild.level, firstChild.weight, firstChild.profit);
          if (firstChild.bound > maxProfit)
            priorityQueue.enqueue(firstChild);
            Node secondChild = new Node();
            secondChild.level = current.level + 1;
            secondChild.weight = current.weight;
            secondChild.profit = current.profit;
            secondChild.copyList(current.contains);
            secondChild.add(current.level+1);
            secondChild.bound = bound(secondChild.level, secondChild.weight, secondChild.profit);
            if (secondChild.bound > maxProfit) priorityQueue.enqueue(secondChild);
          }
        }
      }

  private int bound (int item, int weight, int price) {
    int bound = price;
    int totalSize = weight;
    int itemsInSack = item + 1;
    if (weight > maxWeight) return 0;
    while (itemsInSack < numberOfItems && totalSize + itemWeights[itemsInSack] <= maxWeight) {
      bound += itemProfits[itemsInSack];
      totalSize += itemWeights[itemsInSack];
      itemsInSack++;
    }
    if (itemsInSack < numberOfItems) bound += (maxWeight - totalSize) * (itemProfits[itemsInSack]/ itemWeights[itemsInSack]);
    return bound;
  }
}
